/*
 * @lc app=leetcode.cn id=39 lang=golang
 *
 * [39] 组合总和
 */

// @lc code=start

import (
	"sort"
	"strconv"
	"strings"
)

func combinationSum(candidates []int, target int) [][]int {

	tmp := make([]int, 0)
	res := make([][]int, 0)
	var dfs func(res int)
	dfs = func(num int) {
		if num < 0 {
			return
		}
		if num == 0 {
			t := make([]int, len(tmp))
			copy(t, tmp)
			res = append(res, t)
			return
		}
		for i := 0; i < len(candidates); i++ {
			tmp = append(tmp, candidates[i])
			dfs(num - candidates[i])
			tmp = tmp[:len(tmp)-1]
		}
		return
	}
	dfs(target)
	only := make(map[string][]int)
	for i := 0; i < len(res); i++ {
		k, v := toString(res[i])
		only[k] = v
	}
	res = [][]int{}
	for _, v := range only {
		res = append(res, v)
	}
	return res
}

func toString(nums []int) (string, []int) {
	sort.Ints(nums)
	str := make([]string, 0, len(nums))
	for _, v := range nums {
		str = append(str, strconv.FormatInt(int64(v), 10))
	}
	return strings.Join(str, ""), nums
}

// @lc code=end
